#include "bigint.h"
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

const int BASE = 10000;

int * MyRealloc(int * arr, size_t oldSize, size_t newSize)
{
	int *tmp = new int[newSize];
	for(size_t i = 0; i < min(oldSize, newSize); ++i)
	{
		tmp[i] = arr[i];
	}
	delete [] arr;
	return tmp;
}
void BigInt::Reverse()
{
	size_t n = this -> RealSize();
	for(size_t i = 0; i < this -> RealSize() / 2; ++i)
	{
		swap((*this)[i], (*this)[n - i - 1]);
	}
}
BigInt::BigInt()
	:	virSize(4), 
		realSize(0),
		digArray(new int[4]),
		sign(false)
{

}
BigInt::BigInt(BigInt const& bigNum)
{
	if(this == &bigNum) return;
	virSize = bigNum.virSize;
	realSize = bigNum.realSize;
	digArray = new int[virSize];
	for(size_t i = 0; i < virSize; ++i)
	{
		digArray[i] = bigNum[i];
	}
	sign = bigNum.sign;	
}
BigInt::BigInt(int num)
	:	virSize(4), 
		realSize(0),
		digArray(new int[4]),
		sign(num < 0)
{
	if(num < 0)
	{
		num *= -1;
	}
	if(num == 0)
	{
		this -> Push(num);
	}
	while(num)
	{
		this -> Push(num%BASE);
		num /= BASE;
	}
	//this -> Reverse();
}
BigInt:: ~BigInt()
{
	delete [] digArray;
	virSize = 0 ;
	realSize = 0;
	sign = false;
}
size_t BigInt::RealSize() const
{
	return realSize;
}
bool BigInt::GetSign() const
{
	return sign;
}
void BigInt::SetSign(bool f)
{
	sign = f;
}
void BigInt::Push(int num)
{
	if(realSize == virSize)
	{
		virSize *= 2;
		digArray = MyRealloc(digArray, virSize / 2, virSize);
	}
	digArray[ realSize++ ] = num;
}
int BigInt::Pop()
{
	int ans = digArray[realSize - 1];
	--realSize;
	if(realSize * 2 < virSize && virSize > 4) 
	{
		virSize /= 2;
		digArray = MyRealloc(digArray, virSize * 2, virSize);
	}
	return ans;
}
void BigInt::Clear()
{
	delete [] digArray;
	realSize = 0;
	virSize = 4;
	sign = false;
	digArray = new int [virSize];
}
int& BigInt::operator [](size_t x) const
{
	return digArray[x];
}
void BigInt::Swap(BigInt & b)
{
	swap(b.digArray, (*this).digArray);
	swap(b.sign, (*this).sign);
	swap(b.virSize, (*this).virSize);
	swap(b.realSize, (*this).realSize);
}
BigInt& BigInt::operator =(BigInt const &  bigNum)
{
	if(this != &bigNum) 
		BigInt(bigNum).Swap(*this);	
	return (*this);
}
BigInt & BigInt::operator +=(BigInt const& bigNum)
{
	(*this) = (*this) + bigNum;
	return (*this);
}
BigInt & BigInt::operator -=(BigInt const& bigNum)
{
	(*this) = (*this) - bigNum;
	return (*this);
}
BigInt & BigInt::operator *=(BigInt const& bigNum)
{
	(*this) = (*this) * bigNum;
	return (*this);
}
int CharToInt( char c)
{
	if(c >= '0' && c <= '9')
	{
		return c - '0';
	}
	return 10000;
}
string IntToStr(int x)
{
	string ans;
	int dig = BASE / 10;
	while(x || dig)
	{
		if( x / dig != 0)
		{
			ans += x / dig + '0';
		}
		else
			ans +="0";
		x = x - ((x / dig) * dig);
		dig /= 10;
	}
	if(ans=="") return "0000";
	return ans;
}
void StrToBigInt(string const & s, BigInt& num)
{
	int tmp = 0;
	int dig = 1;
	num.Clear();
	size_t i = s.size();
	if(s[0] == '-')
	{
		num.SetSign(true);
	}
	for( i = i - 1; ; --i)
	{
		tmp += CharToInt(s[i]) * dig;
		dig *= 10;
		if(dig == BASE)
		{
			num.Push(tmp);
			tmp = 0;
			dig = 1;
		}
		if(s[0] == '-' && i==1) break; 
		if( i == 0 ) break;
	}
	if(tmp != 0)
	{
		num.Push(tmp);
	}
	return;
}
string BigIntToStr(BigInt const& num)
{
	string s;
	if(num.RealSize() == 0) return "0";
	for(size_t i = num.RealSize() - 1; i>=0; --i)
	{
		s += IntToStr(num[i]);
		if(i == num.RealSize() -1 ) 
		{
			string tr;
			bool f = false;
			for(size_t i = 0; i < 4; ++i)
			{
				if(s[i] == '0' && !f) continue;
				f = true;
				tr += s[i];
			}
			s = tr;
		}
		if( i == 0) break;
	}
	if(num.GetSign()) 
	{
		s = "-" + s;
	}
	return s;
}
BigInt operator -(BigInt const & bigNum)
{
	BigInt a = BigInt(bigNum);
	a.SetSign(!a.GetSign());
	return a;
}
bool operator <(BigInt const &  bigNumA, BigInt const & bigNumB)
{
	if(bigNumA.RealSize() < bigNumB.RealSize())
	{
		return true;
	}
	if(bigNumA.RealSize() > bigNumB.RealSize())
	{
		return false;
	}
	for(size_t i = bigNumA.RealSize() - 1; ; --i)
	{
		if(bigNumA[i] < bigNumB[i])
		{
			return true;
		} 
		if(bigNumA[i] > bigNumB[i])
		{
			return false;
		}
		if(!i) break;
	}
	return false;
}
bool operator >(BigInt const &  bigNumA, BigInt const & bigNumB)
{
	return ( bigNumB < bigNumA );
}
bool operator <=(BigInt const &  bigNumA, BigInt const & bigNumB)
{
	return !(bigNumA > bigNumB);
}
bool operator >=(BigInt const &  bigNumA, BigInt const & bigNumB)
{
	return (!(bigNumA < bigNumB));
}
bool operator ==(BigInt const &  bigNumA, BigInt const & bigNumB)
{
	if(bigNumA.RealSize() != bigNumB.RealSize())
	{
		return false;
	}
	for(size_t i = bigNumA.RealSize(); ; --i )
	{
		if(bigNumA[i] != bigNumB[i]) 
		{
			return false;
		}
		if(!i) break;
	}
	return true;
}
bool operator !=(BigInt const &  bigNumA, BigInt const & bigNumB)
{
	 return !(bigNumA == bigNumB);
}
BigInt operator +(BigInt const & bigNumA, BigInt const & bigNumB)
{
	if(bigNumA.GetSign() == bigNumB.GetSign())
	{
		BigInt* ans = new BigInt();
		int p = 0;
		for(size_t i = 0 ; i < max(bigNumA.RealSize(), bigNumB.RealSize()); ++i)
		{
			if(bigNumA.RealSize() > i)
			{
				p += bigNumA[i];
			}
			if(bigNumB.RealSize() > i)
			{
				p += bigNumB[i];
			}
			ans->Push(p % BASE);
			p /= BASE;
		}
		while(p)
		{
			ans->Push(p % BASE);
			p /= BASE;
		}
		ans -> SetSign(bigNumA.GetSign()); 
		return (*ans);
	}
	
	if(bigNumA.GetSign() == true) return bigNumB - -bigNumA;
	return bigNumA - -bigNumB;
	
}
BigInt operator -(BigInt const & bigNumA, BigInt const & bigNumB)
{
	if(bigNumA.GetSign() == bigNumB.GetSign())
	{
		BigInt* minuend = new BigInt();
		BigInt* subtr = new BigInt();
		if(bigNumA > bigNumB)
		{
			(*minuend) = bigNumA;
			(*subtr) = bigNumB;
		}
		else
		{
			(*minuend) = bigNumB;
			(*subtr) = bigNumA;
			minuend -> SetSign( !(minuend -> GetSign()) );
		}
		int p = 0;
		size_t i = 0;
		for(i = 0; i < subtr->RealSize(); ++i)
		{
			if((*minuend)[i] - (*subtr)[i] - p < 0) 
			{
				(*minuend)[i] += BASE;
				(*minuend)[i] -= ((*subtr)[i] + p);
				p = 1;
			}
			else
			{
				(*minuend)[i] -= ((*subtr)[i] + p);
				p = 0;
			}		
		}
		while(p)
		{
			if((*minuend)[i] - p < 0) 
			{
				(*minuend)[i] += BASE;
				(*minuend)[i] -= p;
				p = 1;
			}
			else
			{
				(*minuend)[i] -= p;
				p = 0;
			}
			++i;
		}
		while((*minuend)[minuend->RealSize() - 1] == 0 && minuend->RealSize() != 1)
		{
			minuend->Pop();
		}
		return *minuend;
	}
	return bigNumA + -bigNumB;
}
BigInt operator *(BigInt const & bigNumA, BigInt const & bigNumB)
{
	BigInt *ans = new BigInt();
	if(bigNumA.GetSign() == bigNumB.GetSign())
	{
		ans -> SetSign(false);
	}
	else
	{
		ans -> SetSign(true);
	}
	for(size_t i = 0; i < bigNumA.RealSize(); ++i)
	{
		for(size_t j = 0; j < bigNumB.RealSize(); ++j)
		{
			while(i + j + 1 >= ans -> RealSize())
			{
				ans -> Push(0);
			}
			(*ans)[i + j] += bigNumA[i] * bigNumB[j];
			(*ans)[i + j + 1] += (*ans)[i + j] / BASE;
			(*ans)[i + j] %= BASE;
		}
	}
	while((*ans)[ans->RealSize() - 1] == 0 && ans->RealSize()!=0)
	{
		ans->Pop();
	}
	return *ans;
}

BigInt operator /(BigInt const & bigNumA, BigInt const & bigNumB)
{
	BigInt *ans = new BigInt(0);
	if((int)bigNumA.RealSize() - (int)bigNumB.RealSize() < 0)
	{
		return *ans;
	}
	if(bigNumA.GetSign() == bigNumB.GetSign())
	{
		ans -> SetSign(false);
	}
	else
	{
		ans -> SetSign(true);
	}
	BigInt *now = new BigInt();
	
	for(size_t i = bigNumA.RealSize() - bigNumB.RealSize() + 1; i < bigNumA.RealSize(); ++i)
	{
		now -> Push(bigNumA[i]);
	}
	for(size_t i = bigNumA.RealSize() - bigNumB.RealSize(); ; --i)
	{
		(*now) *= BigInt(BASE);
		(*now) += bigNumA[i];
		if((*now) < bigNumB)
		{
			ans -> Push(0);
			if(i == 0) break;
			continue;
		}
		
		int left = 1;
		int right = BASE - 1;
		int k = 0;
		while(left + 1 < right)
		{
			k  = (left + right) / 2;
			if(bigNumB * BigInt(k) <= (*now))
			{
				left = k ;
			}
			else
			{
				right = k;
			}
		}
		k = left;
		(*now) -= BigInt(k) * bigNumB;
		ans -> Push(k);
		if(i == 0) break;
	}
	ans -> Reverse();
	while((*ans)[ans -> RealSize() - 1] == 0)
	{
		ans -> Pop();
	}
	
	return *ans;
}
//*/
ostream & operator <<(ostream & out, BigInt const & bigNum)
{
	out << BigIntToStr(bigNum);
	return out;
}
istream & operator >>(istream & in, BigInt & bigNum)
{
	string s;
	in >> s;
	StrToBigInt(s,bigNum);
	return in;
}
